A conventional broadband circuit switched communications network, for example a telephony network or a mobile phone network, comprises a plurality of nodes, at which are provided node equipment, the nodes connected by a plurality of communications links, the links comprising link equipment. The node equipment may comprise, for example a telecommunications switch apparatus, and the links may comprise a terrestrial link, eg an optical fiber link or coaxial cable or a wireless link.
An increasing range of services are delivered over such networks, including as examples, video on demand, video conferencing, distance learning, and internet services. Such services involve delivering different traffic data types, eg voice traffic, video or computer data traffic, having different characteristics, some types of traffic being more sensitive to delay than others and the different traffic types having different ranges of bitrate requirements. These services may involve delivery of data from a single source to a single destination (point to point) from a single source to many destinations (point to multipoint) or from a plurality of sources to a plurality of destinations (multipoint to multipoint). Such services place heavy requirements for routing of connections supporting these services over a network.
Conventional route finding methods, such as Dijkstra's shortest path algorithm, are capable of finding a single route for a single connection (E W Dijkstra, "A Note on Two Problems in Connection with Graphs", Numerische
Mathematik 1, pg 269, 1959). However, using a shortest path routing algorithm on a connection-by-connection basis can lead to sub-optimal or even highly congested network routing solutions. Additionally, in a telecommunications network, there are constraints other than finding the shortest route to consider. For example, it may be useful to take into account traffic flowing through the network resulting from other connections, and link and node bandwidth capacities.
In WO 96/31969 there is disclosed a method of routing traffic from a communications network which uses a genetic algorithm search routine to find optimum sets of paths between nodes in a network for routing of traffic on a point to point connection basis with the object of minimizing a number of communications channels used, and to reduce a risk of a communications system being unable to handle a high volume of traffic.
In WO 96/31969, a set of shortest paths forms the basis for an initial string population of the genetic algorithm. Routes are selected according to a fitness criteria which includes a user specified weighting based on a number of channels required to support traffic, utilization of links represented as a number of links whose capacity could be exceeded, and a user specified "path cost" comprising a sum of costs of a plurality of links of a path between nodes. The user can vary the fitness criteria by altering the respective weighting given to the path cost, utilization, and number of channels in order to customize the genetic algorithm process to select for these criteria according to an importance as reflected in the user specified weightings.
However, shortest path routing, even as optimized by genetic algorithm technique, cannot provide solutions for point to multipoint routing. Further, shortest path routing cannot deal with service requests for mixed traffic data types.